class MySingleLinkedList {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;//代表链表的头结点

    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void display(ListNode newHead) {
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void addLast(int val) {
        ListNode node = new ListNode(val);
        ListNode cur = head;
        if (head == null) {
            head = node;
            return;
        }
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    //创建环结点
    public void createLoop() {
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = head.next;
    }

    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

public class Demo2_10 {
    //环形链表
    //给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
    //如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
    public static void main(String[] args) {
        MySingleLinkedList msl = new MySingleLinkedList();
        msl.addLast(1);
        msl.addLast(4);
        msl.addLast(10);
        msl.addLast(15);
        msl.addLast(5);
        msl.createLoop();
        MySingleLinkedList.ListNode ret = msl.detectCycle(msl.head);
        System.out.println(ret.val);
    }
}
